Section: New Results

Efficient Filtering Algorithms for Generic Constraints (filtering)

Participants : Nicolas Beldiceanu, Xavier Lorca, Thierry Petit.

Counting constraints We identified a family of counting constraints for which performing a complete filtering is a tractable problem. We provided a generalized arc-consistency algorithm and its specialization to some well-known global constraints. For some of them the obtained time complexity is linear in the sum of domain sizes, which improve or equals the best known results in the literature.

The corresponding paper A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints was published at the 22th International Joint Conference on Artificial Intelligence (IJCAI'11 ) [23] .